package hot100;

public class RemoveNthFromEnd {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //快慢指针，快指针领先n个位置
        ListNode slow = head,fast = head;
        for (int i = 0; i < n; i++) fast = fast.next;
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode pre = preHead;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            pre = pre.next;
        }

        pre.next = slow.next;
        return preHead.next;

    }
}
